题目分析

题目描述的比较复杂，简单说来就是set方法第一个参数为key，将第二个参数value和第三个参数timestamp都放在其中，取出时只能看到时间戳之前的字符串，比如在key为foo，时刻为1时插入一个字符串bar，那么取出foo时在时刻1之后才能看到bar，在时刻1之前无法看到，同理如果在时刻4时放入bar2，那么在时刻4后bar2会替换bar，此后只能看到bar2了，但是在时刻1和时刻4之间只能看到bar。而且本题的时间戳时递增的，这一点非常重要，小伙伴们能够根据有序的线索得到哪些重要信息呢？

二分查找

我们使用哈希表记录TimeMap，其中键就是题目中的存储键key，值是一个可变数组，其中每一个元素都是一个二元组，包括时间和值两个数据。现在本题就变成在一个有序数组中，查找指定时间之前的索引位置。就是一个经典的二分查找问题，相信小伙伴们能够很轻松的写出来，直接看代码即可。

算法的时间复杂度为$O(nlog(n))$，空间复杂度为$O(n)$

下面是C++语言的题解

class TimeMap {
private:
    unordered_map<string, vector<pair<int, string>>> map;

public:
    /** Initialize your data structure here. */
    TimeMap() {

    }

    void set(string key, string value, int timestamp) {
        map[key].push_back({ timestamp, value });
    }

    string get(string key, int timestamp) {
        if (map[key].size() == 0 || timestamp < map[key][0].first) { return ""; }
        int left = 0, right = map[key].size() - 1;
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (map[key][mid].first > timestamp) {
                right = mid - 1;
            }
            else {
                left = mid;
            }
        }
        return map[key][left].second;
    }
};

下面是Kotlin语言的题解

class TimeMap() {
    private val dic = HashMap<String, ArrayList<Pair<Int, String>>>()
    /** Initialize your data structure here. */


    fun set(key: String, value: String, timestamp: Int) {
        val tmp = dic.getOrDefault(key, ArrayList())
        tmp.add(Pair(timestamp, value))
        dic[key] = tmp
    }

    fun get(key: String, timestamp: Int): String {
        val tmp = dic.getOrDefault(key, ArrayList())
        if (tmp.isEmpty() || tmp[0].first > timestamp) { return "" }
        var left = 0
        var right = tmp.size - 1
        while (left < right) {
            val mid = (left + right + 1) shr 1
            if (tmp[mid].first > timestamp) {
                right = mid - 1
            } else {
                left = mid
            }
        }
        return tmp[left].second
    }
}

刷题总结

这个题目的难度不大，主要是能否充分利用有序的特点进行解答，抽出问题的本质，相信小伙伴们都能够轻松写出本题。